home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Software Vault: The Gold Collection
/
Software Vault - The Gold Collection (American Databankers) (1993).ISO
/
cdr53
/
pctv4n_1.zip
/
LINKLIST.PAS
< prev
next >
Wrap
Pascal/Delphi Source File
|
1993-06-10
|
14KB
|
331 lines
UNIT LinkList;
{$X+} { Allow function calls as "procedures" }
{----------------------------------------------------------------
This unit provides a base "linked list" object that can be used
for linked records and objects. The data and methods in the
base object take care of the linked list management functions.
----------------------------------------------------------------}
INTERFACE
TYPE
PLinkNode = ^TLinkNode; {-------------- LINKED LIST NODE TYPE }
TLinkNode = RECORD
PrevNode : PLinkNode; { Previous linked node }
TheItem : Pointer; { Pointer to linked item }
NextNode : PLinkNode; { Next linked node }
END;
PLinkList = ^TLinkList; {------------ LINKED LIST OBJECT TYPE }
TLinkList = OBJECT
NumNodes : Integer; { Current node count }
BaseNode : PLinkNode; { Starting node }
CONSTRUCTOR Init;
DESTRUCTOR Done; VIRTUAL;
FUNCTION ItemCount : Integer;
FUNCTION ItemIndex(Item : Pointer) : Integer;
FUNCTION ListEmpty : Boolean;
FUNCTION FirstItem : Pointer;
FUNCTION LastItem : Pointer;
FUNCTION LastNode : PLinkNode;
FUNCTION NodeForIndex(Index : Integer) : PLinkNode;
FUNCTION NodeForItem(Item : Pointer) : PLinkNode;
FUNCTION ItemForIndex(Index : Integer) : Pointer;
FUNCTION AppendItem(Item : Pointer) : Boolean;
FUNCTION DeleteItem(Item : Pointer) : Boolean;
FUNCTION DeleteIndex(Index : Integer) : Boolean;
FUNCTION InsertBefore(Target,Item : Pointer) : Boolean;
FUNCTION InsertAfter(Target,Item : Pointer) : Boolean;
FUNCTION DeleteAll : Boolean;
END;
IMPLEMENTATION
CONSTRUCTOR TLinkList.Init;
{Initialize a new TLinkList object and set up a null BaseNode.}
BEGIN
BaseNode := NIL;
NumNodes := 0;
END; {---------------------------------------- CONSTRUCTOR Init }
DESTRUCTOR TLinkList.Done;
{Disposes of a TLinkList object and its linked records.}
VAR AThis,APrev : PLinkNode;
BEGIN
DeleteAll;
END; {----------------------------------------- DESTRUCTOR Done }
FUNCTION TLinkList.ItemIndex(Item : Pointer) : Integer;
{Returns the index of the "Item" or -1 if not in the list.}
VAR AThis : PLinkNode;
NItem : Integer;
BEGIN
IF (NumNodes = 0) THEN BEGIN { If the list is empty,... }
ItemIndex := -1; { ... return "-1." }
Exit;
END;
FOR NItem := 0 TO NumNodes DO BEGIN { See if item on list }
AThis := NodeForIndex(NItem);
IF (AThis^.TheItem = Item) THEN BEGIN { YES: Return index }
ItemIndex := NItem;
Exit;
END;
END;
ItemIndex := -1; { NO: Return -1 }
END; {------------------------------------ FUNCTION ItemIndex() }
FUNCTION TLinkList.ItemCount : Integer;
{Returns the number of items currently in the linked list.}
BEGIN
ItemCount := NumNodes;
END; {-------------------------------------- FUNCTION ItemCount }
FUNCTION TLinkList.ListEmpty : Boolean;
{Returns TRUE if the list is empty (i.e., BaseNode^.TheItem = NIL)}
BEGIN
ListEmpty := (NumNodes = 0);
END; {-------------------------------------- FUNCTION ListEmpty }
FUNCTION TLinkList.FirstItem : Pointer;
{Returns the pointer to the first item in the linked list.}
BEGIN
FirstItem := BaseNode^.TheItem;
END; {-------------------------------------- FUNCTION FirstItem }
FUNCTION TLinkList.LastItem : Pointer;
{Returns the pointer to the last item in the linked list.}
BEGIN
LastItem := LastNode^.TheItem;
END; {--------------------------------------- FUNCTION LastItem }
FUNCTION TLinkList.LastNode : PLinkNode;
{Returns the pointer to the last link in the chain.}
VAR AThis, ANext : PLinkNode;
BEGIN
ANext := BaseNode;
WHILE (ANext <> NIL) DO BEGIN
AThis := ANext;
ANext := AThis^.NextNode;
END;
LastNode := AThis;
END; {--------------------------------------- FUNCTION LastNode }
FUNCTION TLinkList.NodeForIndex(Index : Integer) : PLinkNode;
{----------------------------------------------------------------
Returns the pointer to the link node for a given item index.
(Returns NIL if "Index" is not in range [0..NumNodes].
----------------------------------------------------------------}
VAR AThis, ANext : PLinkNode;
N : Integer;
BEGIN
IF ((Index < 0) OR (Index > NumNodes)) THEN BEGIN { Index bad?}
NodeForIndex := NIL; { YES: Return NIL }
Exit;
END;
ANext := BaseNode; { Starting at base,... }
FOR N := 0 TO Index DO BEGIN { ...get the node... }
AThis := ANext; {... having this index. }
ANext := AThis^.NextNode;
END;
NodeForIndex := AThis;
END; {--------------------------------- FUNCTION NodeForIndex() }
FUNCTION TLinkList.NodeForItem(Item : Pointer) : PLinkNode;
{----------------------------------------------------------------
Returns the pointer to the link item for "Item."
(Returns NIL if "Item" is not in the list.)
----------------------------------------------------------------}
VAR AThis, ANext : PLinkNode;
BEGIN
IF (Item = NIL) THEN BEGIN { Return NIL for a NIL item. }
NodeForItem := NIL;
Exit;
END;
ANext := BaseNode; { Starting at base... }
WHILE (ANext <> NIL) DO BEGIN { ...look for a match... }
AThis := ANext; { ...with "Item"... }
ANext := AThis^.NextNode;
IF (AThis^.TheItem = Item) THEN BEGIN { MATCH:... }
NodeForItem := AThis; { Return node pointer }
Exit;
END;
END;
NodeForItem := NIL; { NO MATCH: Return NIL }
END; {---------------------------------- FUNCTION NodeForItem() }
FUNCTION TLinkList.ItemForIndex(Index : Integer) : Pointer;
{----------------------------------------------------------------
Returns the pointer to the item for a given item index.
(Returns NIL if "Index" is not in range [0..NumNodes].
----------------------------------------------------------------}
VAR AThis : PLinkNode;
BEGIN
AThis := NodeForIndex(Index); { Get node pointer for "Index" }
IF (AThis <> NIL) THEN { FOUND NODE:... }
ItemForIndex := AThis^.TheItem { ...return item pointer }
ELSE
ItemForIndex := NIL; { NO NODE: Return NIL }
END; {--------------------------------- FUNCTION ItemForIndex() }
FUNCTION TLinkList.AppendItem(Item : Pointer) : Boolean;
{----------------------------------------------------------------
Adds "Item" to the end of linked list and increments the count.
Returns TRUE if successful; FALSE if not.
NOTE: If "Item" is already in the list, it is deleted and moved
to the end list. (This prevents the list from having duplicate entries for the same Item.)
----------------------------------------------------------------}
VAR AThis, ALast : PLinkNode;
BEGIN
IF (NumNodes > 0) THEN { If there are nodes... }
DeleteItem(Item); { ...delete any existing "Item"... }
IF (MaxAvail > SizeOf(TLinkNode)) THEN BEGIN { Get node space }
GetMem(AThis,SizeOf(TLinkNode));
AThis^.TheItem := Item; { Assign "Item" to node }
IF (NumNodes > 0) THEN BEGIN { NOT FIRST NODE:... }
ALast := LastNode; { Make "Item" node the last node }
AThis^.NextNode := NIL;
AThis^.TheItem := Item;
AThis^.PrevNode := ALast;
ALast^.NextNode := AThis;
END
ELSE BEGIN { FIRST NODE:... }
BaseNode := AThis; { ...Fix pointers }
AThis^.PrevNode := NIL;
AThis^.NextNode := NIL;
END;
Inc(NumNodes); { Increment the node count }
AppendItem := TRUE; { Return TRUE }
END
ELSE { NO MEMORY:... }
AppendItem := FALSE; { ...Return FALSE }
END; {----------------------------------- FUNCTION AppendItem() }
FUNCTION TLinkList.DeleteItem(Item : Pointer) : Boolean;
{Deletes "Item" from the linked list and decrements the item count.}
VAR AThis : PLinkNode;
BEGIN
AThis := NodeForItem(Item); { Get node pointer for "Item" }
IF (AThis = NIL) THEN BEGIN { NO NODE:... }
DeleteItem := FALSE; { ...Return FALSE }
Exit;
END;
WITH AThis^ DO BEGIN { NODE FOUND:... }
IF (PrevNode <> NIL) THEN { NOT BaseNode:... }
PrevNode^.NextNode := NextNode { ...fix Prev's Next }
ELSE { IS BaseNode:... }
BaseNode := NextNode; { ...promote old Next }
IF (NextNode <> NIL) THEN { NOT Last Node:... }
NextNode^.PrevNode := PrevNode; { ...fix Next's Prev }
END;
FreeMem(AThis,SizeOf(TLinkNode)); { Deallocate memory }
Dec(NumNodes); { Decrement node count }
DeleteItem := TRUE; { Return TRUE }
END; {----------------------------------- FUNCTION DeleteItem() }
FUNCTION TLinkList.DeleteIndex(Index : Integer) : Boolean;
{----------------------------------------------------------------
Deletes Item number "Index" from the linked list and decrements
the item count.
NOTE: Returns FALSE if Index not in [0..NumNodes]
----------------------------------------------------------------}
VAR AThis : PLinkNode;
BEGIN
IF ((Index < 0) OR (Index > NumNodes)) THEN BEGIN { Bad Index? }
DeleteIndex := FALSE; { YES: Return FALSE }
Exit;
END;
DeleteIndex := DeleteItem(ItemForIndex(Index)); {Delete item...}
END; {---------------------------------- FUNCTION DeleteIndex() }
FUNCTION TLinkList.InsertBefore(Target,Item : Pointer) : Boolean;
{Inserts "Item" BEFORE "Target" item. If "Target" is not in
the linked list, "Item" is inserted at the head of the list.}
VAR APrev, AThis, ANext : PLinkNode;
BEGIN
IF (Item = NIL) THEN BEGIN { NIL Item:... }
InsertBefore := FALSE; { ...Return FALSE }
Exit;
END;
DeleteItem(Item); { Delete Item (if on list) }
IF (MaxAvail > SizeOf(TLinkNode)) THEN BEGIN { If space... }
GetMem(AThis,SizeOf(TLinkNode)); { ...allocate node }
IF (Target = NIL) THEN { NIL Target:... }
ANext := BaseNode { ...new node is BaseNode }
ELSE BEGIN { Otherwise... }
ANext := NodeForItem(Target); { ...get Target node }
IF (ANext = NIL) THEN { NIL Target: ... }
ANext := BaseNode; { ...new node is BaseNode }
END;
WITH AThis^ DO BEGIN { Now adjust pointers... }
APrev := ANext^.PrevNode;
IF (APrev <> NIL) THEN
APrev^.NextNode := AThis;
PrevNode := APrev;
NextNode := ANext;
TheItem := Item;
ANext^.PrevNode := AThis;
END;
IF (AThis^.PrevNode = NIL) THEN { 1st node? }
BaseNode := AThis; { YES: assign it as BaseNode }
Inc(NumNodes); { Increment node count }
InsertBefore := TRUE; { Return TRUE }
END
ELSE { NO MEMORY: ... }
InsertBefore := FALSE; { ...Return FALSE }
END; {--------------------------------- FUNCTION InsertBefore() }
FUNCTION TLinkList.InsertAfter(Target,Item : Pointer) : Boolean;
{Inserts "Item" AFTER "Target" item. If "Target" is not in
the linked list, "Item" is inserted at the end of the list.}
VAR APrev, AThis, ANext : PLinkNode;
BEGIN
IF (Item = NIL) THEN BEGIN { NIL Item:... }
InsertAfter := FALSE; { ...Return FALSE }
Exit;
END;
DeleteItem(Item); { Delete Item (if on list) }
IF (MaxAvail > SizeOf(TLinkNode)) THEN BEGIN { If space... }
GetMem(AThis,SizeOf(TLinkNode)); { ...allocate node }
IF (Target = NIL) THEN { NIL Target?... }
APrev := LastNode { YES: Set Prev to LastNode }
ELSE BEGIN { NO: ... }
APrev := NodeForItem(Target); { Set Prev to Target }
IF (APrev = NIL) THEN { NIL Target? }
APrev := LastNode; { YES: Set Prev to LastNode }
END;
WITH AThis^ DO BEGIN { Now adjust pointers... }
ANext := APrev^.NextNode;
IF (ANext <> NIL) THEN
ANext^.PrevNode := AThis;
PrevNode := APrev;
NextNode := ANext;
TheItem := Item;
APrev^.NextNode := AThis;
END;
Inc(NumNodes); { Increment node count }
InsertAfter := TRUE; { Return TRUE }
END
ELSE { NO MEMORY: ... }
InsertAfter := FALSE; { ...Return FALSE }
END; {---------------------------------- FUNCTION InsertAfter() }
FUNCTION TLinkList.DeleteAll : Boolean;
{----------------------------------------------------------------
Disposes of all the link nodes, leaving set to NIL BaseNode.
Only return FALSE if one of the delete operations failed.
----------------------------------------------------------------}
VAR GoodReturn : Boolean;
BEGIN
GoodReturn := TRUE; { Assume we will succeed }
IF (NumNodes = 0) THEN BEGIN { If the list is empty... }
BaseNode := NIL; { ...ensure BaseNode is NIL }
DeleteAll := TRUE; { ...Return TRUE }
Exit;
END;
WHILE (NumNodes > 0) DO { List NOT empty: ... }
IF (NOT DeleteIndex(NumNodes-1)) THEN
GoodReturn := FALSE; { Delete failed (?) }
BaseNode := NIL; { Ensure BaseNode is NIL }
DeleteAll := GoodReturn; { Reflect outcome in return }
END; {-------------------------------------- FUNCTION DeleteAll }
END. {------------------------------------------- UNIT LinkList }